package com.leetcode.algorithm.y22.m06;

import java.util.Arrays;

/**
 * 1385. 两个数组间的距离值
 * 
 * https://leetcode.cn/problems/find-the-distance-value-between-two-arrays/
 * 
 * @author jie.deng
 *
 */
class Question1385Solution01 {

	public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
		Arrays.sort(arr2);

		int cnt = 0;
		for (int i = 0; i < arr1.length; i++) {
			int idx = binarySearch(arr2, arr1[i]);
			if (idx == 0) {
				if (arr2[idx] - arr1[i] > d) {
					cnt += 1;
				}
			} else if (idx == arr2.length) {
				if (arr1[i] - arr2[idx - 1] > d) {
					cnt += 1;
				}
			} else {
				if (arr2[idx] - arr1[i] > d && arr1[i] - arr2[idx - 1] > d) {
					cnt += 1;
				}
			}
		}
		return cnt;
	}

	private int binarySearch(int[] arr, int num) {
		int left = 0;
		int right = arr.length;
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (arr[mid] == num) {
				return mid;
			} else if (arr[mid] < num) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return left;
	}

}